package com.xyj.week02;

import java.util.*;

/**
 * 插入、删除、随机取一个元素，时间复杂度为常数级别，允许重复元素
 */
public class T2 {

    public static void main(String[] args) {
        T2 t1 = new T2();
        System.out.println("初始数据结构为"+t1);
        System.out.println(t1.insert(1));
        System.out.println("插入值之后数据结构为: "+t1);
        System.out.println(t1.remove(1));
        System.out.println("删除值之后数据结构为: "+t1);
        HashSet<Object> objects = new HashSet<>();
//        System.out.println(t1.remove(1));
//        System.out.println("删除一个值之后数据结构为："+t1);
    }

    public T2(){
        this.list= new ArrayList<>();
        this.valToIndex=new HashMap<>();
    }
    @Override
    public String toString() {
        return "Hash表为："+this.valToIndex.toString()
                +"\n 数组为："+this.list.toString();
    }

    public ArrayList<Integer> list;

    public HashMap<Integer, List<Integer>> valToIndex;


    /**
     * 添加一个元素
     * @param num 元素
     * @return 是否添加成功
     */
    public Boolean insert(Integer num){
        //如果已经存在的话
        if (valToIndex.containsKey(num)){
            valToIndex.get(num).add(list.size());
            list.add(num);
            return false;
        }
        List<Integer> integerList =new ArrayList<>();
        integerList.add(list.size());
        valToIndex.put(num,integerList);
        list.add(num);
        return true;
    }

    /**
     * 删除一个元素
     * @param num 元素
     * @return 是否删除成功
     */
    public Boolean remove (Integer num){
        List<Integer> temp = valToIndex.get(num);
        if(temp==null){
            return false;
        }
        int item = temp.remove(0);
        if(temp.size()==0) {
            valToIndex.remove(num);
        }
        if(list.size()-1==item) {
            list.remove(item);
        }else {
            Integer lastItem = list.remove(list.size()-1);//最后一个元素的内容
            list.set(item, lastItem);
            //对结尾元素的调整 将最后一个数字对应的索引集合找到 然后删除原有索引 更新现有索引
            temp = valToIndex.get(lastItem);
//            temp.remove(temp.size()-1);
            temp.remove((Integer)list.size());//这个过程还是比较耗时的
            temp.add(item);
        }
        return true;
    }

    /**
     * 随机获取一个元素
     */
    public Integer getRandom (){
        Random random = new Random();
        return list.get(random.nextInt(list.size()));
    }



}
